import java.util.*;

/*
 * @lc app=leetcode.cn id=1319 lang=java
 *
 * [1319] 连通网络的操作次数
 */

// @lc code=start
class Solution {
    // 并查集
    // 1. 线的数量至少为n-1,否则无法全联通
    // 2. 3个并查集需要移动两根线连接，故需要操作的数目为并查集数目-1
    public int makeConnected(int n, int[][] connections) {
        int len = connections.length;//线段数目
        if(len < n-1) return -1;//线的数目不够，返回-1即可
        //先要去数并查集的数目
        UnionFind uf = new UnionFind(n);//n个节点
        for(int[] t:connections){
            uf.union(t[0], t[1]);
        }
        //全部并起来之后去数联通分量的个数，我感觉我之前写过的。
        Set<Integer> parent = new HashSet<>();
        for(int i=0 ;i<n;i++){
            parent.add(uf.find(uf.parent[i]));//把每个节点的父节点放入parent
        }
        return parent.size()-1;
    }

    class UnionFind{
        int[] parent;
        public UnionFind(int n){
            parent = new int[n];
            for(int i = 0 ;i<n;i++){
                parent[i] = i;//先指向自己
            }
        }

        public int find(int x){
            return parent[x]==x? x: (parent[x]=find(parent[x]));
        }

        public void union(int x ,int y){
            int px = find(x);
            int py = find(y);
            if(px == py) return;
            parent[py] = px;
        }
    }
}
// @lc code=end

